A case study on financial ratios via cross%2Dgraph quasi%2Dbicliques.

Birds Bring Flues%3F Mining Frequent and High Weighted Cliques from Birds Migration Networks.

Negative correlations in collaboration concepts and algorithms.

Protein binding hot spots and the residue%2Dresidue pairing preference a water exclusion perspective.

Sequence%2Dbased identification of interface residues by an integrative profile combining hydrophobic and evolutionary information.

Modeling Protein Interacting Groups by Quasi%2DBicliques Complexity

Discovery of Migration Habitats and Routes of Wild Bird Species by Clustering and Association Analysis.

High Functional Coherence in k%2DPartite Protein Cliques of Protein Interaction Networks.

Applications of Emerging Patterns for Microarray Gene Expression Data Analysis.

Emerging Pattern Based Classification.

Emerging Patterns.
Abstract. Emerging patterns (EPs) are associations of features whose frequencies increase significantly from one class to another. They have been proven useful to build powerful classifiers and to help establishing diagnosis. Because of the huge search space, mining and representing EPs is a hard task for large datasets. Thanks to the use of recent results on condensed representations of frequent closed patterns, we propose here an exact condensed representation of EPs. We also give a method to provide EPs with the highest growth rates, we call them strong emerging patterns (SEPs). In collaboration with the Philips company, experiments show the interests of SEPs. 1 Introduction The characterization of classes and classification are significant fields of researchin data mining and machine learning. Initially introduced in [5], emerging patterns (EPs) are patterns whose frequency strongly varies between two data sets(i.e., two classes). EPs characterize the classes in a quantitative and qualitative way. Thanks to their capacity to emphasize the distinctions between classes,EPs enable to build classifiers [6] or to propose a help for diagnosis. Nevertheless, mining EPs in large datasets remains a challenge because of the very highnumber of candidate patterns. In this paper, we propose two contributions for the efficient extraction ofemerging patterns. One originality of our approach is to take advantage of recent progresses on the condensed representations of closed patterns [9]. Firstly,we propose an exact condensed representation of the emerging patterns for a dataset. Contrary to the borders approach (Section 2) which provides the EPswith a lower bound of their growth rate, this condensed representation easily enables to know the exact growth rate for each emerging pattern. Secondly, wepropose a method to easily provide the emerging patterns having the best growth rates (we call them &amp;quot; strong emerging patterns &amp;quot;). This work is also justified byrequests from providers of data. In our collaboration with the Philips company, one notices in practice a high number of EPs and the strong emerging patternsare particularly useful to bring more synthetic and more exploitable results.
%27Double water exclusion%27 a hypothesis refining the O%2Dring theory for the hot spots at protein interfaces.

PADS a simple yet effective pattern%2Daware dynamic search method for fast maximal frequent pattern mining.

Efficient mining of distance%2Dbased subspace clusters.

Negative Generator Border for Effective Pattern Maintenance.
Abstract. In this paper, we study the maintenance of frequent patterns in the context of the generator representation. The generator representation is a concise and lossless representation of frequent patterns. We effectively maintain the generator representation by systematically expanding its Negative Generator Border. According to our literature review, no prior work has studied the maintenance of the generator representation. To illustrate the proposed maintenance idea, a new algorithm is developed to maintain the generator representation for support threshold adjustment. Our experimental results show that the proposed algorithm is significantly faster than other state-of-the-art algorithms. This proposed maintenance idea can also be extended to other representations of frequent patterns as demonstrated in this paper. 1
Interacting Amino Acid Preferences of 3D Pattern Pairs at the Binding Sites of Transient and Obligate Protein Complexes.
To assess the physico-chemical characteristics of protein-protein interactions, protein sequences and overall structural folds have been analyzed previously. To highlight this, discovery and examination of amino acid patterns at the binding sites defined by structural proximity in 3-dimensional (3D) space are essential. In this paper, we investigate the interacting preferences of 3D pattern pairs discovered separately in transient and obligate protein complexes. These 3D pattern pairs are not necessarily sequence-consecutive, but each residue in two groups of amino acids from two proteins in a complex is within certain ˚A threshold to most residues in the other group. We develop an algorithm called AApairs by which every pair of interacting proteins is represented as a bipartite graph, and it discovers all maximal quasi-bicliques from every bipartite graph to form our 3D pattern pairs. From 112 and 2533 highly conserved 3D pattern pairs discovered in the transient and obligate complexes respectively, we observe that Ala and Leu is the highest occuring amino acid in interacting 3D patterns of transient (20.91%) and obligate (33.82%) complexes respectively. From the study on the dipeptide composition on each side of interacting 3D pattern pairs, dipeptides Ala-Ala and Ala-Leu are popular in 3D patterns of both transient and obligate complexes. The interactions between amino acids with large hydrophobicity difference are present more in the transient than in the obligate complexes. On contrary, in obligate complexes, interactions between hydrophobic residues account for the top 5 most occuring amino acid pairings.
Interacting Amino Acid Preferences of 3D Pattern Pairs at the Binding Sites of Transient and Obligate Protein Complexes.
To assess the physico-chemical characteristics of protein-protein interactions, protein sequences and overall structural folds have been analyzed previously. To highlight this, discovery and examination of amino acid patterns at the binding sites defined by structural proximity in 3-dimensional (3D) space are essential. In this paper, we investigate the interacting preferences of 3D pattern pairs discovered separately in transient and obligate protein complexes. These 3D pattern pairs are not necessarily sequence-consecutive, but each residue in two groups of amino acids from two proteins in a complex is within certain ˚A threshold to most residues in the other group. We develop an algorithm called AApairs by which every pair of interacting proteins is represented as a bipartite graph, and it discovers all maximal quasi-bicliques from every bipartite graph to form our 3D pattern pairs. From 112 and 2533 highly conserved 3D pattern pairs discovered in the transient and obligate complexes respectively, we observe that Ala and Leu is the highest occuring amino acid in interacting 3D patterns of transient (20.91%) and obligate (33.82%) complexes respectively. From the study on the dipeptide composition on each side of interacting 3D pattern pairs, dipeptides Ala-Ala and Ala-Leu are popular in 3D patterns of both transient and obligate complexes. The interactions between amino acids with large hydrophobicity difference are present more in the transient than in the obligate complexes. On contrary, in obligate complexes, interactions between hydrophobic residues account for the top 5 most occuring amino acid pairings.
Quasi%2Dbicliques Complexity and Binding Pairs.

Mining and Ranking Generators of Sequential Patterns.
Sequential pattern mining first proposed by Agrawal and Srikant has received intensive research due to its wide range applicability in many real-life domains. Various improvements have been proposed which include mining a closed set of sequential patterns. Sequential patterns supported by the same sequences in the database can be considered as belonging to an equivalence class. Each equivalence class contains patterns partially-ordered by sub-sequence relationship and having the same support. Within an equivalence class, the set of maximal and minimal patterns are referred to as closed patterns and generators respectively. Generators used together with closed patterns can provide additional information which closed patterns alone are not able to provide. Also, as generators are the minimal members, they are preferable over closed patterns for model selection and classification based on the Minimum Description Length (MDL) principle. Several algorithms have been proposed for mining closed sequential patterns, but none so far for mining sequential generators. This paper fills this research gap by investigating properties of sequential generators and proposing an algorithm to efficiently mine sequential generators. The algorithm works on a three-step process of search space compaction, non-generator pruning and a final filtering step. We also introduce ranking of mined generators and propose mining of a unique generator per equivalence class. Performance study has been conducted on various synthetic and real benchmark datasets. They show that mining generators can be as fast as mining closed patterns even at low support thresholds. 
Maximal Quasi%2DBicliques with Balanced Noise Tolerance Concepts and Co%2Dclustering Applications.
The rigid all-versus-all adjacency required by a maximal biclique for its two vertex sets is extremely vulnerable to missing data. In the past, several types of quasi-bicliques have been proposed to tackle this problem, however their noise tolerance is usually unbalanced and can be very skewed. In this paper, we improve the noise tolerance of maximal quasi-bicliques by allowing every vertex to tolerate up to the same number, or the same percentage, of missing edges. This idea leads to a more natural interaction between the two vertex sets— a balanced most-versus-most adjacency. This generalization is also non-trivial, as many large-size maximal quasi-biclique subgraphs do not contain any maximal bicliques. This observation implies that direct expansion from maximal bicliques may not guarantee a complete enumeration of all maximal quasi-bicliques. We present important properties of maximal quasi-bicliques such as a bounded closure property and a fixed point property to design efficient algorithms. Maximal quasi-bicliques are closely related to co-clustering problems such as documents and words co-clustering, images and features coclustering, stocks and financial ratios co-clustering, etc. Here, we demonstrate the usefulness of our concepts using a new application—a bioinformatics example— where prediction of true protein interactions is investigated.
A new concise representation of frequent itemsets using generators and a positive border.
A complete set of frequent itemsets can get undesirably large due to redundancy when the minimum support threshold is low or when the database is dense. Several concise representations have been previously proposed to eliminate the redundancy. Generator based representations rely on a negative border to make the representation lossless. However, the number of itemsets on a negative border sometimes even exceeds the total number of frequent itemsets. In this paper, we propose to use a positive border together with frequent generators to form a lossless representation. A positive border is usually orders of magnitude smaller than its corresponding negative border. A set of frequent generators plus its positive border is always no larger than the corresponding complete set of frequent itemsets, thus it is a true concise representation. The generalized form of this representation is also proposed. We develop an efficient algorithm, called GrGrowth, to mine generators and positive borders as well as their generalizations. The GrGrowth algorithm uses the depth-first-search strategy to explore the search space, which is much more efficient than the breadth-first-search strategy adopted by most of the existing generator mining algorithms. Our experiment results show that the GrGrowth algorithm is significantly faster than level-wise algorithms for mining generator based representations, and is comparable to the state-of-the-art algorithms for mining frequent closed itemsets. 
Emerging Technologies in Knowledge Discovery and Data Mining

Distance Based Subspace Clustering with Flexible Dimension Partitioning.

Mining statistically important equivalence classes and delta%2Ddiscriminative emerging patterns.
The support-confidence framework is the most common measure used in itemset mining algorithms, for its antimonotonicity that effectively simplifies the search lattice. This computational convenience brings both quality and statistical flaws to the results as observed by many previous studies. In this paper, we introduce a novel algorithm that produces itemsets with ranked statistical merits under sophisticated test statistics such as chi-square, risk ratio, odds ratio, etc. Our algorithm is based on the concept of equivalence classes. An equivalence class is a set of frequent itemsets that always occur together in the same set of transactions. Therefore, itemsets within an equivalence class all share the same level of statistical significance regardless of the variety of test statistics. As an equivalence class can be uniquely determined and concisely represented by a closed pattern and a set of generators, we just mine closed patterns and generators, taking a simultaneous depth-first search scheme. This parallel approach has not been exploited by any prior work. We evaluate our algorithm on two aspects. In general, we compare to LCM and FPclose which are the best algorithms tailored for mining only closed patterns. In particular, we compare to epMiner which is the most recent algorithm for mining a type of relative risk patterns, known as minimal emerging patterns. Experimental results show that our algorithm is faster than all of them, sometimes even multiple orders of magnitude faster. These statistically ranked patterns and the efficiency have a high potential for reallife applications, especially in biomedical and financial fields where classical test statistics are of dominant interest.
Evolution and Maintenance of Frequent Pattern Space When Transactions Are Removed.
Abstract. This paper addresses the maintenance of discovered frequent patterns when a batch of transactions are removed from the original dataset. We conduct an in-depth investigation on how the frequent pattern space evolves under transaction removal updates using the concept of equivalence classes. Inspired by the evolution analysis, an effective and exact algorithm TRUM is proposed to maintain frequent patterns. TRUM maintains frequent patterns efficiently by updating only the affected equivalence classes. Experimental results demonstrate that our algorithm outperforms representative state-of-the-art algorithms. 1


Workshop BioDM%2707 %2D An Overview.

Discovering Patterns of DNA Methylation Rule Mining with Rough Sets and Decision Trees

Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency Matrix A One%2Dto%2DOne Correspondence and Mining Algorithms.
 Maximal biclique (also known as complete bipartite) subgraphs can model many applications in web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that: (i) the number of closed patterns in the adjacency matrix of G is even; (ii) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G; and (iii) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a non-duplicated enumeration, in particular for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph respectively. We evaluate the high efficiency of our algorithm by comparing it to state-of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even; but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. 
Strong Compound%2DRisk Factors Efficient Discovery Through Emerging Patterns and Contrast Sets.

Data Mining for Biomedical Applications

Minimum Description Length Principle Generators Are Preferable to Closed Patterns.

Minimum Description Length Principle Generators Are Preferable to Closed Patterns.

COWES Clustering Web Users Based on Historical Web Sessions.
Abstract. Clustering web users is one of the most important research topics in web usage mining. Existing approaches cluster web users based on the snapshots of web user sessions. They do not take into account the dynamic nature of web usage data. In this paper, we focus on discovering novel knowledge by clustering web users based on the evolutions of their historical web sessions. We present an algorithm called COWES to cluster web users in three steps. First, given a set of web users, we mine the history of their web sessions to extract interesting patterns that capture the characteristics of their usage data evolution. Then, the similarity between web users is computed based on their common interesting patterns. Then, the desired clusters are generated by a partitioning clustering technique. Web user clusters generated based on their historical web sessions are useful in intelligent web advertisement and web caching. 1

Efficient Mining of Large Maximal Bicliques.
 Maximal biclique (also known as complete bipartite) subgraphs can model many applications in web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that: (i) the number of closed patterns in the adjacency matrix of G is even; (ii) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G; and (iii) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a non-duplicated enumeration, in particular for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph respectively. We evaluate the high efficiency of our algorithm by comparing it to state-of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even; but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. 
Performance Analysis of MF%2DTDMA Multi%2DCarrier Demultiplexer%2FDemodulators %28MCDs%29 in the Presence of Critical Degrading Factors.


Mining Temporal Indirect Associations.

Bayesian Approaches to Ranking Sequential Patterns Interestingness.

Positive Borders or Negative Borders How to Make Lossless Generator Based Representations Concise.
A complete set of frequent itemsets can get undesirably large due to redundancy. Several representations have been proposed to eliminate the redundancy. Existing generator based representations rely on a negative border to make the representation lossless. However, negative borders of generators are often very large. The number of itemsets on a negative border sometimes even exceeds the total number of frequent itemsets. In this paper, we propose to use a positive border together with frequent generators to form a lossless representation. A set of frequent generators plus its positive border is always no larger than the corresponding complete set of frequent itemsets, thus it is a true concise representation. The generalized form of this representation is also proposed. We develop an efficient algorithm, called GrGrowth, to mine generators and positive borders as well as their generalizations. 1

Discovering motif pairs at interaction sites from protein sequences on a proteome%2Dwide scale.


Mining Succinct Systems of Minimal Generators of Formal Concepts.
Abstract. Formal concept analysis has become an active field of study for data analysis and knowledge discovery. A formal concept C is determined by its extent (the set of objects that fall under C) and its intent (the set of properties or attributes covered by C). The intent for C, also called a closed itemset, is the maximum set of attributes that characterize C. The minimal generators for C are the minimal subsets of C’s intent which can similarly characterize C. This paper introduces the succinct system of minimal generators (SSMG) as a minimal representation of the minimal generators of all concepts, and gives an efficient algorithm for mining SSMGs. The SSMGs are useful for revealing the equivalence relationship among the minimal generators, which may be important for medical and other scientific discovery; and for revealing the extent-based semantic equivalence among associations. The SSMGs are also useful for losslessly reducing the size of the representation of all minimal generators, similar to the way that closed itemsets are useful for losslessly reducing the size of the representation of all frequent itemsets. The removal of redudancies will help human users to grasp the structure and information in the concepts.
A Correspondence Between Maximal Complete Bipartite Subgraphs and Closed Patterns.
For an undirected graph ¢ without self-loop, we prove: (i) that the number of closed patterns in the adjacency matrix of ¢ is even; (ii) that the number of the closed patterns is precisely double the number of maximal complete bipartite subgraphs of ¢ ; (iii) that for every maximal complete bipartite subgraph, there always exists a unique and distinct pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, we can efficiently enumerate all maximal complete bipartite subgraphs by using algorithms for mining closed patterns which have been extensively studied in the data mining field. 1

Relative risk and odds ratio a data mining perspective.
We are often interested to test whether a given cause has a given effect. If we cannot specify the nature of the factors involved, such tests are called model-free studies. There are two major strategies to demonstrate associations between risk factors (ie. patterns) and outcome phenotypes (ie. class labels). The first is that of prospective study designs, and the analysis is based on the concept of “relative risk”: What fraction of the exposed (ie. has the pattern) or unexposed (ie. lacks the pattern) individuals have the phenotype (ie. the class label)? The second is that of retrospective designs, and the analysis is based on the concept of “odds ratio”: The odds that a case has been exposed to a risk factor is compared to the odds for a case that has not been exposed. The efficient extraction of patterns that have good relative risk and/or odds ratio has not been previously studied in the data mining context. In this paper, we investigate such patterns. We show that this pattern space can be systematically stratified into plateaus of convex spaces based on their support levels. Exploiting convexity, we formulate a number of sound and complete algorithms to extract the most general and the most specific of such patterns at each support level. We compare these algorithms. We further demonstrate that the most efficient among these algorithms is able to mine these sophisticated patterns at a speed comparable to that of mining frequent closed patterns, which are patterns that satisfy considerably simpler conditions. 1.
Use of extreme patient samples for outcome prediction from gene expression data.
Motivation: Patient outcome prediction using microarray technologies is an important application in bioinformatics. Based on patients ’ genotypic microarray data, predictions are made to estimate patients ’ survival time and their risk of tumor metastasis or recurrence. So, accurate prediction can potentially help to provide better treatment for patients. Results: We present a new computational method for patient outcome prediction. In the training phase of this method, we make use of two types of extreme patient samples: shortterm survivors who got an unfavorable outcome within a short period and long-term survivors who were maintaining a favorable outcome after a long follow-up time. These extreme training samples yield a clear platform for us to identify relevant genes whose expression is closely related to the outcome. The selected extreme samples and the relevant genes are then integrated by a support vector machine to build a prediction model, by which each validation sample is assigned a risk score that falls into one of special pre-defined risk groups. We apply this method to several public data sets. In most cases, patients in high and low risk groups stratified by our method have clearly distinguishable outcome status as seen in their Kaplan-Meier curves. We also show that the idea of selecting only extreme patient samples for training is effective for improving the prediction accuracy when different gene selection methods are used. Contact:

DNAFSMiner a web%2Dbased software toolbox to recognize two types of functional sites in DNA sequences.

Guest Editors%27 Introduction Data Mining in Bioinformatics.

Mining border descriptions of emerging patterns from dataset pairs.%2
This paper presents an overview of pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval
Using Fixed Point Theorems to Model the Binding in Protein%2DProtein Interactions.

Structural geography of the space of emerging patterns.

Mining border descriptions of emerging patterns from dataset pairs.%2
This paper presents an overview of pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval
Use of Built%2Din Features in the Interpretation of High%2Ddimensional Cancer Diagnosis Data..

Selection of Patient Samples and Genes for Outcome Prediction.
Gene expression profiles with clinical outcome data enable monitoring of disease progression and prediction of patient survival at the molecular level. We present a new computational method for outcome prediction. Our idea is to use an informative subset of original training samples. This subset consists of only short-term survivors who died within a short period and long-term survivors who were still alive after a long follow-up time. These extreme training samples yield a clear platform to identify genes whose expression is related to survival. To find relevant genes, we combine two feature selection methods — entropy measure and Wilcoxon rank sum test — so that a set of sharp discriminating features are identified. The selected training samples and genes are then integrated by a support vector machine to build a prediction model, by which each validation sample is assigned a survival/relapse risk score for drawing Kaplan-Meier survival curves. We apply this method to two data sets: diffuse large-B-cell lymphoma (DLBCL) and primary lung adenocarcinoma. In both cases, patients in high and low risk groups stratified by our risk scores are clearly distinguishable. We also compare our risk scores to some clinical factors, such as International Prognostic Index score for DLBCL analysis and tumor stage information for lung adenocarcinoma. Our results indicate that gene expression profiles combined with carefully chosen learning algorithms can predict patient survival for certain diseases. 1.
A Tree%2DBased Approach to the Discovery of Diagnostic Biomarkers for Ovarian Cancer.

Twelve C2H2 zinc%2Dfinger genes on human chromosome 19 can be each translated into the same type of protein after frameshifts.

Discovery of Binding Motif Pairs from Protein Complex Structural Data and Protein Interaction Sequence Data.

Twelve C2H2 zinc%2Dfinger genes on human chromosome 19 can be each translated into the same type of protein after frameshifts.

Incremental Maintenance on the Border of the Space of Emerging Patterns.

Using amino acid patterns to accurately predict translation initiation sites.
this paper, we present an in-silico method to predict translation initiation sites in cDNA or mRNA sequences. This method consists of three sequential steps as follows. In the first step, candidate features are generated using #-gram amino acid patterns. In the second step, a small number of top-ranked features are selected by an entropy-based algorithm. In the third step, a classification model is built to recognize true TISs by applying support vector machines or ensembles of decision trees to the selected features. We have tested our method on several independent data sets, including two public ones and our own extracted sequences. The experimental results achieved are better than those reported previously using the same data sets. Our high accuracy not only demonstrates the feasibility of our method, but also indicates that there are &#034;amino acid&#034; motifs around TIS in cDNA and mRNA sequences
Feature Space Transformation for Better Understanding Biological and Medical Classifications.

DeEPs A New Instance%2DBased Lazy Discovery and Classification System.

Feature Space Transformation and Decision Results Interpretation.

From Informatics to Bioinformatics.
Informatics has helped in launching molecular biology into the genomic era. It appears certain that informatics will continue to be a major factor in the success of molecular biology in the post-genome era. In this paper, we describe advances made in data integration and data mining technologies that are relevant to molecular biology and biomedical sciences. In particular, we discuss some past and present research results on topics such as (a) the taming of autonomous heterogeneous distributed data sources, (b) the prediction of immunogenic peptides, (c) the discovery of gene structure features, (d) the classification of gene expression profiles, and (e) the extraction of protein interaction information from literature. Keywords: Bioinformatics, data integration, data warehousing, Kleisli, epitope prediction, FIMM, transcription start site recognition, Dragon, gene expression analysis, PCL, protein interaction extraction, PIES.
Mean%2Dentropy discretized features are effective for classifying high%2Ddimensional biomedical data.
Abstract. This paper studies an empirical feature selection heuristics for classifying high-dimensional bio-medical data. A feature’s discriminating power can be measured by its entropy value. Based on this idea, we do not consider those features that are ignored by the entropy idea. Such a selection can usually reduce the dimensionality of the data by 90–95%. Then we rank the remaining features, and select features whose entropy is smaller than the average of all the remaining features ’ entropies. This round of selection can usually further reduce two thirds of the features. So, we can achieve a reduction from tens of thousands of features to only hundreds of important features. Furthermore, we also observe that learning algorithms, including our new tree-committee classifier, generally improve their accuracy after the feature selection. This heuristics appears to be more systematic than the prevailing use of specific numbers of top-ranked features for classification. 1
Discovery of significant rules for classifying cancer diagnosis data.

Ensembles of Cascading Trees.
We introduce a new method, called CS4, to construct committees of decision trees for classification. The method considers different top-ranked features as the root nodes of member trees. This idea is particularly suitable for dealing with high-dimensional bio-medical data as top-ranked features in this type of data usually possess similar merits for classification. To make a decision, the committee combines the power of individual trees in a weighted manner. Unlike Bagging or Boosting which uses bootstrapped training data, our method builds all the member trees of a committee using exactly the same set of training data. We have tested these ideas on UCI data sets as well as recent bio-medical data sets of gene expression or proteomic profiles that are usually described by more than 10,000 features. All the experimental results show that our method is efficient and that the classification performance are superior to C4.5 family algorithms. 
Bioinformatics Adventures in Database Research.
Informatics has helped launch molecular biology into the genomic  era. It appears certain that informatics will remain a major contributor to molecular  biology in the post-genome era. We discuss here data integration and datamining  in bioinformatics, as well as the role that database theory played in these topics.
Using Rules to Analyse Bio%2Dmedical Data A Comparison between C4.5 and PCL.
For easy comprehensibility, rules are preferrable to non-linear kernel  functions in the analysis of bio-medical data. In this paper, we describe two rule  induction approaches---C4.5 and our PCL classifier---for discovering rules from  both traditional clinical data and recent gene expression or proteomic profiling  data. C4.5 is a widely used method, but it has two weaknesses, the single coverage  constraint and the fragmentation problem, that affect its accuracy. PCL is a new  rule-based classifier that overcomes these two weaknesses of decision trees by  using many significant rules. We present a thorough comparison to show that our  PCL method is much more accurate than C4.5, and it is also superior to Bagging  and Boosting in general.
Simple rules underlying gene expression profiles of more than six subtypes of acute lymphoblastic leukemia %28ALL%29 patients.

Solving the Fragmentation Problem of Decision Trees by Discovering Boundary Emerging Patterns.

Geography of Differences between Two Classes of Data.

Identifying good diagnostic gene groups from gene expression profiles using the concept of emerging patterns .


Identifying good diagnostic gene groups from gene expression profiles using the concept of emerging patterns.


Making Use of the Most Expressive Jumping Emerging Patterns for Classification.
. Classification aims to discover a model from training data that can  be used to predict the class of test instances. In this paper, we propose the use  of jumping emerging patterns (JEPs) as the basis for a new classifier called the  JEP-Classifier. Each JEP can capture some crucial difference between a pair of  datasets. Then, aggregating all JEPs of large supports can produce more potent  classification power. Procedurally, the JEP-Classifier learns the pair-wise features  (sets of JEPs) contained in the training data, and uses the collective impacts contributed  by the most expressive pair-wise features to determine the class labels of  the test data. Using only the most expressive JEPs in the JEP-Classifier strengthens  its resistance to noise in the training data, and reduces its complexity (as there  are usually a very large number of JEPs). We use two algorithms for constructing  the JEP-Classifier which are both scalable and efficient. These algorithms make  use of the border...
Emerging Patterns and Classification.

The Space of Jumping Emerging Patterns and Its Incremental Maintenance Algorithms.
The concept of jumping emerging patterns  (JEPs) has been proposed to describe those discriminating  features which only occur in the positive  training instances but do not occur in the  negative class at all; JEPs have been used to  construct classifiers which generally provide better  accuracy than the state-of-the-art classifiers  such as C4.5. The algorithms for maintaining the  space of jumping emerging patterns (JEP space)  are presented in this paper. We prove that JEP  spaces satisfy the property of convexity. Therefore  JEP spaces can be concisely represented  by two bounds: consisting respectively of the  most general elements and the most specific elements.  In response to insertion of new training  instances, a JEP space is modified by operating  on its boundary elements and the boundary elements  of the JEP spaces associated with the new  instances. This strategy completely avoids the  need to go back to the most initial step to build  the new JEP space. In addition, our ...
Making Use of the Most Expressive Jumping Emerging Patterns for Classification.
. Classification aims to discover a model from training data that can  be used to predict the class of test instances. In this paper, we propose the use  of jumping emerging patterns (JEPs) as the basis for a new classifier called the  JEP-Classifier. Each JEP can capture some crucial difference between a pair of  datasets. Then, aggregating all JEPs of large supports can produce more potent  classification power. Procedurally, the JEP-Classifier learns the pair-wise features  (sets of JEPs) contained in the training data, and uses the collective impacts contributed  by the most expressive pair-wise features to determine the class labels of  the test data. Using only the most expressive JEPs in the JEP-Classifier strengthens  its resistance to noise in the training data, and reduces its complexity (as there  are usually a very large number of JEPs). We use two algorithms for constructing  the JEP-Classifier which are both scalable and efficient. These algorithms make  use of the border...
Instance%2DBased Classification by Emerging Patterns.
. Emerging patterns (EPs), namely itemsets whose supports change significantly  from one class to another, capture discriminating features that sharply  contrast instances between the classes. Recently, EP-based classifiers have been  proposed, which first mine as many EPs as possible (called eager-learning) from  the training data and then aggregate the discriminating power of the mined EPs  for classifying new instances. We propose here a new, instance-based classifier  using EPs, called DeEPs, to achieve much better accuracy and efficiency than  the previously proposed EP-based classifiers. High accuracy is achieved because  the instance-based approach enables DeEPs to pinpoint all EPs relevant to a test  instance, some of which are missed by the eager-learning approaches. High efficiency  is obtained using a series of data reduction and concise data-representation  techniques. Experiments show that DeEPs&#039; decision time is linearly scalable over  the number of training instances and...
CAEP Classification by Aggregating Emerging Patterns.
3 and Jinyan Li 2 1
Efficient Mining of Emerging Patterns Discovering Trends and Differences.
We introduce a new kind of patterns, called emerging patterns (EPs), for knowledge discovery from databases. EPs are defined as itemsets whose supports increase significantly  from one dataset to another. EPs can capture emerging trends in timestamped databases, or useful contrasts between data classes. EPs have been proven useful: we have used them to build very powerful classifiers, which are more accurate than C4.5 and CBA, for many datasets. We believe that EPs with low to medium support, such as 1%-- 20%, can give useful new insights and guidance to experts, in even &#034;well understood&#034; applications.  The efficient mining of EPs is a challenging problem, since (i) the Apriori property no longer holds for EPs, and (ii) there are usually too many candidates for high dimensional databases or for small support thresholds such as 0.5%. Naive algorithms are too costly. To solve this problem, (a) we promote the description of large collections of itemsets using their concise borders (the pa...
Efficient Mining of High Confidience Association Rules without Support Thresholds.

Interestingness of Discovered Association Rules in Terms of Neighborhood%2DBased Unexpectedness.
One of the central problems in knowledge discovery is the development of good measures of interestingness of discovered patterns. With such measures, a user needs to manually examine only the more interesting rules, instead of each of a large number of mined rules. Previous proposals of such measures include rule templates, minimal rule cover, actionability, and unexpectedness in the statistical sense or against user beliefs. In this paper we will introduce neighborhood-based interestingness by considering unexpectedness in terms of neighborhood-based parameters. We first present some novel notions of distance between rules and of neighborhoods of rules. The neighborhood-based interestingness of a rule is then defined in terms of the pattern of the fluctuation of confidences or the density of mined rules in some of its neighborhoods. Such interestingness can also be defined for sets of rules (e.g. plateaus and ridges) when their neighborhoods have certain properties. We c...
